A partial response is used as a modulation code used in a magnetic recording and reproducing apparatus or an optical recording and reproducing apparatus. Of kinds of the partial response, PRS (1,1) (class I), PRS (1,-1), PRS (1,0 -1) (class IV) and so on are used frequently. An arithmetic circuit 101 shown in FIG. 6(a) uses the PRS (1,0,-1). Arithmetic circuits 102, 103 shown in FIG. 6(b) use the PRS (1,-1). A system polynomial G(D) of the PRS (1,0,-1) is G(D)=1-D.sup.2 and a system polynomial G(D) of the PRS (1,-1) is G(D)=1+D, where reference letter D represents a delay operator.
The arithmetic circuit 101 is a circuit which successively outputs data of 1, 0 and -1 when an independent logic 1 is input. The arithmetic circuits 102, 103 are circuits which successively output data of 1 and -1 when an independent logic 1 is input.
The arithmetic circuit 101 (PRS(1,0,-1)) shown in FIG. 6(a) has the system polynomial of G(D)=1-D.sup.2 and hence always calculates input data y.sub.k inputted at a certain sampling time k as a two previous sample y.sub.k-2. Accordingly, an odd number sample and an even number sample are substantially independent of each other and can be regarded as independent series of the partial response PRS (1,-1). The circuit shown in FIG. 6(a) is equivalent to a circuit shown in FIG. 6(b) in which the odd and even number samples of input data are respectively supplied to and processed by the arithmetic circuits 102, 103 for calculating the partial response PRS (1,-1) by switching a switch 104 and outputs of the arithmetic circuits are synthesized by a switch 105 to be output.
Decoding in which the arithmetic circuits 102, 103 (PRS (1,-1)) are used with being interleaved is substantially the same as decoding carried out by the arithmetic circuit 101 (PRS(1,0,-1)). Here, the partial response PRS (1,0,-1) will be explained by way of example.
The partial response PRS (1,0,-1) itself has the property of permitting an error to be propagated and, hence, one bit error caused under a certain condition, may cause a fatal error. Therefore, in order to prevent such an error from being caused, it is necessary to pre-code data before recording them. This pre-coding can be carried out by effecting a reverse conversion of the partial response.
FIG. 7 shows a total arrangement of a conventional for modulating and demodulating the partial response through such precoding. In FIG. 7, a pre-coder 111 carries out a process of 1/(1-D.sup.2).
Recorded data are converted by the pre-coder 111 into pre-coded data varying between a value 1 of the recorded data and a value -1 thereof by utilizing a correlation between data of the recorded data. The thus converted data are output to a recording channel circuit 112.
The recording channel circuit 112 is not an explicitly provided circuit rather a function which is inherently possessed by a magnetic recording and reproducing system and is represented in FIG. 7 as an equivalent circuit. In this circuit (that is, when the data are magnetically recorded and then reproduced), an arithmetic processing circuit 113 subject the output from the pre-coder 111 to an arithmetic processing of (1-D).
At this time, a noise generated in a practical magnetic recording channel is treated as one to be added to a result of the calculation by an adder 114. Data to which the noise is added (data reproduced after magnetically recorded) are from the recording channel circuit 12 an arithmetic processing circuit 115. The arithmetic processing circuit 115 subjects the output from the recording channel circuit 112 to an arithmetic processing of (1+D).
As shown in FIG. 8, a signal output from the recording channel circuit 112 is set at any one of three levels of {-2,0,+2} if the input signal level ranges between values .+-.2. When the signal is decoded by a decoder 116 (FIG. 7) so as to be an original binary data (1 or 0), it can be considered to take a three-level detecting method using fixed threshold values or a Viterbi decoding which is a maximum likelihood decoding method.
The three-level detecting method is a method in which two threshold levels having predetermined fixed values are respectively set between values 0 and +2 and between values 0 and -2 and data are decoded by determining whether a signal level sampled at a sample point is larger or smaller than the threshold levels. The method has an advantage such that the circuit can be very simplified, but it also has a disadvantage such that a detection ability is comparatively low.
On the other hand, the maximum likelihood decoding method (the Viterbi decoding) is a method in which data are decoded by using values at previous and subsequent sample points to detect a series (path) of the data obtained after being decoded and a maximum likelihood series (path) is estimated on the basis thereof. As compared with the three-level detecting method, the maximum likelihood decoding method has high detection ability and can reduce a bit error rate to an extent from two figures to one figure when the same data are decoded by both of the methods.
Next, there will be described an example of a circuit used when the decoder 116 is formed of a Viterbi decoder. Before the circuit is explained, the Viterbi decoding will be explained. Having the system polynomial of 1-D.sup.2, a system using the PRS (1,0,-1) has four states. If data are derived from the system at every other bit, then such derived data form one system (that is, PRS(1,-1)), which has two states because its system polynomial is 1-D.
A state transition diagram of the PRS (1,-1) is shown in FIG. 9. If a value 1 is input when the state of the PRS (1,-1) is a.sub.k-2 =-1, then the state thereof is changed to a.sub.k =+1 and a value 2 is output. If a value -1 is input, then the state thereof is changed to the same state as an original state thereof, i.e., a state of a.sub.k =+1 and a value 0 is output. Further, if a value 1 is input when the state thereof is a.sub.k-2 =+1, then the state thereof is changed to a.sub.k =-1 and a value -2 is output. If a value -1 is input, then the state thereof is changed to the same state as an original state thereof, i.e., a state of a.sub.k =-1 and a value 0 is output.
A trellis diagram (likelihood seeking diagram) (hereinafter referred to as a trellis) corresponding to the state transition diagram shown in FIG. 9 is shown in FIG. 10. In the trellis, if a sample value (which is the output from the arithmetic processing circuit 115 in this case) y.sub.k is input at a certain sampling time k, a branch metric (which corresponds to an instantaneous standard of a likelihood) from the state of a.sub.k -2 to a state of a.sub.k is indicated in the form of a value obtained by multiplying a squared error of the sample value y.sub.k by -1 (-(y.sub.2 -0).sup.2, -(y.sub.2 -2).sup.2, -(y.sub.2 +2).sup.2, . . . ).
The Viterbi decoding finds a path through which a sum of all the branch metrics becomes maximum. Respective path metrics (which correspond to integrals of likelihood path) L.sub.k + and L.sub.k - up to a certain sampling time k under the states of a.sub.k =+1 and a.sub.k =-1 can be represented by using values L.sub.k-2 of the path metrics up to one previous sampling time k-2 as shown in the following equations (1) and (2) . EQU L.sub.k +=max {L.sub.k-2 ++[-(y.sub.k -0).sup.2 ], L.sub.k-2 -+[-(y.sub.k -2).sup.2 ]} (1) EQU L.sub.k -=max {L.sub.k-2 ++[-(y.sub.k +2).sup.2 ], L.sub.k-2 -+[-(y.sub.k -0).sup.2 ]} (2)
Here, max {A,B} represents selection of larger number between the values A and B.
In order to detect a most proper path while computing the metric, three squaring circuits, six adders and two comparators are generally required. Then, instead of calculating every path metric accurately, an algorithm in which a differential metric is used can be used in order to simplify the circuit.
A Viterbi algorithm used when there are only two states will be considered. The Viterbi algorithm is operated such that it determines data while selecting one path in which likelihood in reaching each state at a certain time k becomes largest. The above-mentioned decoding circuit (decoder 116) is used to realize the Viterbi algorithm accurately.
Difference between path metrics (a differential metric) in the states of a.sub.k =+1, -1 can be expressed by the following equation: EQU .DELTA.Lk=Lk+-L.sub.k - (3).
In case of EQU L.sub.k-2 ++[-(y.sub.k -0).sup.2 ]&gt;L.sub.k-2 -+[-(y.sub.k -2).sup.2 ]
(the case of large likelihood in transition from a state of a.sub.k-2 =+1 to a state of a.sub.k =+1), the path metric L.sub.k + is determined from equation (1) as EQU L.sub.k-2 ++[-(y.sub.k -0).sup.2 ].
In case of EQU L.sub.k-2 ++[-(y.sub.k -0).sup.2 ].ltoreq.L.sub.k-2 -+[-(y.sub.k -2).sup.2 ]
(the case of large likelihood in transition from a state of a.sub.k-2 =-1 to the state of a.sub.k =+1), the path metric L.sub.k + is determined therefrom as EQU L.sub.k-2 -+[-(y.sub.k -2).sup.2 ].
On the other hand, in case of EQU L.sub.k-2 ++[-(y.sub.k +2).sup.2 ]&gt;L.sub.k-2 -+[-(y.sub.k -0).sup.2 ]
(the case of large likelihood in transition from the state of a.sub.k-2 =+1 to a state of a.sub.k =-1), the path metric L.sub.k - is determined from equation (2) as EQU L.sub.k-2 ++[-(y.sub.k +2).sup.2 ].
In case of EQU L.sub.k-2 ++[-(y.sub.k +2).sup.2 ].gtoreq.L.sub.k-2 -+[-(y.sub.k -0).sup.2 ]
(the case of large likelihood in transition from the state of a.sub.k-2 =-1 to the state of a.sub.k =-1), the path metric L.sub.k - is determined therefrom as EQU L.sub.k-2 -+[-(y.sub.k -2).sup.2 ].
To summarize them, the path metric L.sub.k + has two different values obtained in case of EQU 4&gt;4y.sub.k -.DELTA.L.sub.k-2 (C+ 1)
(case of large likelihood in transition from the state of a.sub.k-2 =+1 to the state of a.sub.k =+1) and in case of EQU 4.gtoreq.4y.sub.k -.DELTA.L.sub.k-2 (C+ 2)
(case of large likelihood in transition from the state of a.sub.k-2 =-1 to the state of a.sub.k =+1). The path metric L.sub.k - has two different values obtained in case of EQU -4&gt;4y.sub.k -.DELTA.L.sub.k-2 (C- 1)
(case of large likelihood in transition from the state of a.sub.k-2 =+1 to the state of a.sub.k =-1) and in case of EQU -4.gtoreq.4y.sub.k -.DELTA.L.sub.k-2 (C- 2)
(case of large likelihood in transition from the state of a.sub.k-2 =-1 to the state of a.sub.k =-1).
Accordingly, the differential metric .DELTA.L.sub.k expressed in equation (3) is varied depending upon each of four cases (=2.times.2), i.e., cases of (C+1) and (C-1), (C+2) and (C-2), (C+1) and (C-2), and (C+2) and (C-1).
In case of 4&gt;4y.sub.k -.DELTA.L.sub.k-2 and -4&gt;4y.sub.k -.DELTA.L.sub.k-2 (case of a survivor path becoming a pattern of a state &lt;+1&gt;.fwdarw. the state &lt;+1&gt; and of the state &lt;+1&gt;.fwdarw. a state &lt;-1&gt;), i.e., of -4&gt;4y.sub.k -.DELTA.L.sub.k-2, the differential metric .DELTA.L.sub.k is ##EQU1##
Further, in case of 4.gtoreq.4y.sub.k -.DELTA.L.sub.k-2 and -4.gtoreq.4y.sub.k -.DELTA.L.sub.k-2 (case of a survivor path becoming a pattern of the state &lt;-1&gt;.fwdarw. the state &lt;-1&gt; and of the state &lt;-1&gt;.fwdarw. the state &lt;+1&gt;), i.e., of 4.gtoreq.4y.sub.k -.DELTA.L.sub.k-2, the differential metric .DELTA.L.sub.k is ##EQU2##
In case of 4&gt;4y.sub.k -.DELTA.L.sub.k-2 and -4.gtoreq.4y.sub.k -.DELTA.L.sub.k-2 (case of a survivor path becoming a pattern of the state &lt;-1&gt;.fwdarw. the state &lt;-1&gt; and the state &lt;+1&gt;.fwdarw. the state &lt;+1&gt;), i.e., of -4.gtoreq.4y.sub.k -.DELTA.L.sub.k-2 &lt;4, the differential metric .DELTA.L.sub.k is ##EQU3##
In case of 4.gtoreq.4y.sub.k -.DELTA.L.sub.k-2 and -4&gt;4y.sub.k -.DELTA.L.sub.k-2 (case of a survivor path becoming a pattern of the state &lt;-1&gt;.fwdarw. the state &lt;-1&gt; and of the state &lt;+1&gt;.fwdarw. the state &lt;+1&gt;), summarization of these equations indicates 4.gtoreq.4y.sub.k -.DELTA.L.sub.k-2 &lt;-4. Therefore, the above case cannot happen.
Judging from the above description, equation (3) can give a value of .DELTA.L.sub.k depending upon size of the term 4y.sub.k -.DELTA.L.sub.k-2 and the value is given as shown in the following equation (4). ##EQU4##
Accordingly, in case of only two states (of a.sub.k =+1 and a.sub.k =-1), only the following three kinds of survivor path patterns are possible;
the state &lt;-1&gt;.fwdarw. the state &lt;-1&gt; and the state &lt;-1&gt;.fwdarw. the state &lt;+1&gt;; PA1 the state &lt;-1&gt;.fwdarw. the state &lt;-1&gt; and the state &lt;+1&gt;.fwdarw. the state &lt;+1&gt;; and PA1 the state &lt;+1&gt;.fwdarw. the state &lt;+1&gt; and the state &lt;+1&gt;.fwdarw. the state &lt;-1&gt;. PA1 the upward divergence (.fwdarw..Arrow-up bold.) in case of 0.ltoreq.y.sub.k -y.sub.p, PA1 the parallel path (.fwdarw..fwdarw.) in case of -2.ltoreq.y.sub.k -y.sub.p &lt;0, and PA1 the downward divergence (.fwdarw..dwnarw.) in case of y.sub.k -y.sub.p &lt;-2 PA1 y.sub.p .rarw.y.sub.k and .beta..rarw.+1 in case of 0.ltoreq.y.sub.k -y.sub.p, PA1 y.sub.p .rarw.y.sub.p and .beta..rarw..beta. in case of -2.ltoreq.y.sub.k -y.sub.p &lt;0, and PA1 y.sub.p .rarw.y.sub.k and .beta..rarw.-1 in case of y.sub.k -y.sub.p -2 (FIG. 11). PA1 the upward divergence (.fwdarw..Arrow-up bold.) in case of 2.ltoreq.y.sub.k -y.sub.p, PA1 the parallel path (.fwdarw..fwdarw.) in case of 0.ltoreq.y.sub.k -y.sub.p &lt;2, and PA1 the downward divergence (.fwdarw..dwnarw.) in case of y.sub.k -y.sub.p &lt;0 PA1 y.sub.p .rarw.y.sub.k and .beta..rarw.+1 in case of 2.ltoreq.y.sub.k -y.sub.p, PA1 y.sub.p .rarw.y.sub.p and .beta..rarw..beta. in case of 0.ltoreq.y.sub.k -y.sub.p &lt;2, and PA1 y.sub.p .rarw.y.sub.k and .beta..rarw.-1 in case of y.sub.k -y.sub.p &lt;0.
Here, the three kinds of possible survivor path patterns are represented by three kinds of two-letter symbols, i.e., .fwdarw..Arrow-up bold., .fwdarw..fwdarw. and .fwdarw..dwnarw..
Since inequalities used for discrimination of cases in equation (4) include a term of 4y.sub.k -.DELTA.L.sub.k-2 as a common comparative element, the value of the term is compared with a value 4 or -4 to determine size of the value. Therefore, it can be determined which of the above survivor path patterns the survivor path pattern is. In other words, calculation of the differential metric permits a survivor path, which survives in a process of the calculation, to be determined without calculating the path metric itself, and data can be decoded on the basis of the obtained survivor path.
When the value of the differential path metric is transformed by change of variables to .DELTA.L.sub.k =4y.sub.p -4.beta. with setting a value y.sub.p as a sample value at a point (location P) where any one of paths except a parallel path (.fwdarw..fwdarw.), i.e., an upward divergence (.fwdarw..Arrow-up bold.) or a downward divergence (.fwdarw..dwnarw.) occurs in the trellis and with setting a value .beta. as a so-called correction term, equation (4) can be expressed as shown in the following equation (5). ##EQU5##
When left and right sides of equation (5) are compared, if an upper or lower equality therein is established, i.e., the upward divergence (.fwdarw..Arrow-up bold.) or the downward divergence (.fwdarw..dwnarw.) of the survivor path pattern occurs, it is understood that the value .beta. has a value 1 or -1.
Accordingly, the value .beta. represents a divergence direction at the point (location p) where the first upward divergence (.fwdarw..Arrow-up bold.) or the first downward divergence (.fwdarw..dwnarw.) caused before the present point occurs (whether the survivor path pattern at the point (location p) is one of the upward divergence (.fwdarw..Arrow-up bold.) or the downward divergence (.fwdarw..dwnarw.).
If the first divergence caused before the present point is the upward divergence (.fwdarw..Arrow-up bold.), for example, i.e., if .beta.=+1 is established, then the survivor path pattern at the present point is determined as
by substituting a value 1 for the value .beta. in the inequality of equation (5) used for discrimination of cases (FIG. 11).
Further, in this case, when the left and right sides of equation (5) are compared, the values .beta. and y.sub.p are updated in a manner of
Similarly, if the first divergence caused before the present point is the downward divergence (.fwdarw..dwnarw.), for example, i.e., if .beta.=-1 is established, then the survivor path pattern at the present point is determined as
by substituting a value 1 for the value .beta. in the inequality of equation (5) used for discrimination of cases. When the left and right sides of equation (5) are compared, the values .beta. and y.sub.p are updated in a manner of
Accordingly, what the value .beta. means in view of equation can be regarded as a role of adding an offset to a threshold value used for determination (this point will be described later on with reference to Tables 1 and 2).
When the upward divergence (.fwdarw..Arrow-up bold.) or the downward divergence (.fwdarw..dwnarw.) of the survivor path pattern occurs, there can be confirmed a path to the point (location k) from the point (location p), where a divergence previous to one at the point (location k) thereof, occurs. Repetition of this confirmation allows data to be decoded.
FIG. 12 is a block diagram showing the decoder 116 for decoding the data on the basis of the above-described Viterbi algorithm. Reproduced data supplied from the recording channel circuit 112 (shown in FIG. 7) are input to a processing circuit 120 or 130, which processes independently an odd string sample or an even string sample thereof. Then, the respective samples are rearranged into their original orders by a synthesizing circuit 141 on the basis of the timing of a change-over signal output by the change-over circuit 1. The thus rearranged samples are.
FIG. 12 shows the detailed arrangement of the processing circuit 120 for processing the even string sample, while it is understood that the processing circuit 130 for processing the odd string sample is similarly arranged.
In the processing circuit 120, the reproduced data supplied from the recording channel circuit 112 are supplied to a subtracting circuit 11 and a register 12b through a switch 14 which is turned on/off at a timing of the odd string sample/the even string sample in response to the change-over signal output by the change-over circuit 1. In other words, the even string sample of the reproduced data are supplied to the subtracting circuit 11 and the register 12b.
The register 12b stores the sample value y.sub.p at one previous divergence point. The subtracting circuit 11 subtracts the value y.sub.p stored in the register 12b from an input even string sample y.sub.k (calculates (y.sub.k -y.sub.p)) and outputs a result of the subtraction to a comparing circuit 13.
The comparing circuit 13 carries out arithmetic processings shown in Tables 1 and 2 in response to the threshold values +2, 0 and -2, the output of the subtracting circuit 11 (y.sub.k -y.sub.p) and the value of a previous .beta., stored in the register 12a, outputting output data shown in Tables 1 and 2 in response to a result of the calculation.
This calculation will be described in detail later on with reference to FIGS. 14 and 15.
TABLE 1 ______________________________________ when .beta. = 1 is established ______________________________________ input y.sub.k - y.sub.p &lt; -2 -2 .ltoreq. y.sub.k - y.sub.p &lt; 0 0 .ltoreq. y.sub.k - y.sub.p condition condition A B C pattern rule of y.sub.p .rarw. y.sub.k y.sub.k .rarw. y.sub.p y.sub.p .rarw. y.sub.k update .beta. .rarw. -1 .beta. .rarw. .beta. .beta. .rarw. +1 output data new .beta. = -1 new .beta. = * new .beta. = 1 merge = 1 merge = 0 merge = 1 data = 1 data = 0 data = 0 ______________________________________ ##STR1##
TABLE 2 ______________________________________ when .beta. = -1 is established ______________________________________ input y.sub.k - y.sub.p &lt; 0 0 &lt; y.sub.k - y.sub.p .ltoreq. 2 2 .ltoreq. y.sub.k - y.sub.p condition condition D E F pattern rule of y.sub.p .rarw. y.sub.k y.sub.p .rarw. y.sub.p y.sub.p .rarw. y.sub.k update .beta. .rarw. -1 .beta. .rarw. .beta. .beta. .rarw. +1 output data new .beta. = -1 new .beta. = * new .beta. = 1 merge = 1 merge = 0 merge = 1 data = 0 data = 0 data = 1 ______________________________________ ##STR2## As shown in FIG. 13, a shift register 121 is formed as a parallel load/serial shift register arranged such that there are connected in parallel to each other a shift register, in which N selectors Sp.sub.1 to Sp.sub.N and N flip-flops Dp.sub.1 to Dp.sub.N are alternately connected in cascade and a flip-flop Dp.sub.0 is connected at a preceding stage of the first stage selector Sp.sub.1, and a serial shift register in which N selectors Sm.sub.1 to Sm.sub.N and N flip-flops Dm.sub.1 to Dm.sub.N are
Reference letter N represents a processing unit length (bit number) used for subjecting the reproduced data (the even string sample) to the Viterbi decoding.
A value 0 is input as a signal B or D to the first stage selector Sp.sub.1 or Sm.sub.1, and a survivor path pattern signal (merge) supplied from the comparing circuit 13 is input as a signal A or C thereto through the flip-flop Dp.sub.0. Either of the signals (either of the signals A and B or either of the signals C or D) is selected in correspondence with the survivor path pattern signal (merge) and the data (data) supplied from the comparing circuit 13 and then output to the flip-flop Dp.sub.1 or Dm.sub.1.
The survivor path pattern signal (merge) is a flag indicating whether or not a result of discrimination of input condition is the parallel path, in other words, whether or not the state can be changed. The data (data) is also a flag indicating whether or not the state has already been changed. For example, merge=1 and data=0 indicate that the state could be changed ##STR3## but the state has not actively been changed actually.
As shown in Tables 1 and 2, the comparing circuit 13 sets merge=1 when the upward divergence or the downward divergence occurs; and the comparing circuit 13 sets merge=0 when the parallel path occurs.
Data latched by the preceding stage flip-flop DP.sub.n-1 are input as the signal A or C to the selectors Sp.sub.n or Sm.sub.n (n=2, . . . , N) excluding the first stage selector Sp.sub.1 or Sm.sub.1, and data latched by the preceding stage flip-flop Dm.sub.n-1 are input as the signal B or D thereto. Either of the signals A and B or either of the signals C and D is selected in correspondence with the survivor path pattern signal (merge) and the data (data) supplied from the comparing circuit 13 and then output to the succeeding stage flip-flop Dp.sub.n+1 or Dm.sub.n+1, respectively.
TABLE 3 ______________________________________ output of selector Sp.sub.n output of selector Sm.sub.n ______________________________________ merge = 0 A D merge = 1 A C and data = 1 merge = 1 B D and data = 0 ______________________________________
As shown in Table 3, the selector Sp.sub.n (Sm.sub.n) selects and outputs either of the input signals A and B (C and D) in response to the survivor path pattern signal (merge) and the data (data) supplied from the comparing circuit 13.
The flip-flop Dp.sub.n or Dm.sub.n latches an output supplied from the preceding stage selector Sp.sub.n or Sm.sub.n in synchronism with a PLL clock output from a PLL (not shown).
If the arrangement as shown in FIG. 12 is employed, then a squaring circuit becomes unnecessary and it is sufficient to merely provide one adder and two comparators.
Subsequently, an operation carried out by the circuit shown in FIG. 12 when a certain signal is input thereto (now explained with reference to FIGS. 14 and 15 which are timing charts).
When a signal as shown in FIG. 14 is input to the decoder 116 shown in FIG. 12, the comparing circuit 13 and the shift register 121 (shown in FIG. 13) are respectively operated in accordance with Tables 1 and 2 and Table 3 as follows. Initial values of the values y.sub.p and .beta., however, are set as y.sub.p =-2 and .beta.=-1, respectively. &lt;in case of k=0: input y.sub.k =y.sub.0 =1.6; y.sub.p =-2; .beta.=-1&gt;
Since y.sub.k -y.sub.p =1.6-(-2)=3.6&gt;2 is established, an input to the decoder corresponds to the condition pattern F in Table 2. That is, since the upward divergence (sometimes referred to as divergence) occurs, in accordance with Table 2, the value .beta. stored in the register 12a is updated with +1 and the value y.sub.p (the sample value at a time when one previous divergence occurred) stored in the register 12b is updated as y.sub.p =y.sub.0 =1.6.
At the same time, in accordance with Table 2, the comparing circuit 13 outputs the survivor path pattern signal (merge=1) and the data (data=1) to the shift register 121.
Accordingly, in the shift register 121 (shown in FIG. 12), the flip-flop Dp.sub.0 latches the signal of merge=1 (shown in FIG. 15).
&lt;in case of k=1: input y.sub.k =y.sub.1 =0.2; y.sub.p =1.6; .beta.=+1; p=0&gt;
Since -2.ltoreq.y.sub.k -y.sub.p =0.2-1.6=-1.4.ltoreq.0 is established, the input corresponds to the condition pattern B shown in Table 1. That is, since the parallel path occurs, the values .beta. and y respectively stored in the registers 12a and 12b are set as they are (.beta.=1 and y.sub.p =y.sub.0). The comparing circuit 13 outputs the survivor path pattern signal (merge=0) and the data (data=0) to the shift register 121.
In the shift register 121, the flip-flop Dp.sub.0 latches the signal of merge=0. Further, since merge=0 is established, in accordance with Table 3, the signal A of the signal A and B and the signal D of the signals C and D are respectively selected and then output by the selectors Sp.sub.n and Sm.sub.n to the succeeding stage flip-flops Dp.sub.n and Dm.sub.n which latch the signals A and D, respectively.
In case of the parallel path pattern, a signal (bit) latched by the flip-flop Dp.sub.n at an upper stage is latched by the succeeding stage flip-flop DP.sub.n+1 at the same upper stage, and a signal (bit) latched by the flip-flop Dm.sub.n at a lower stage is latched by the succeeding stage flip-flop Dm.sub.n+1 at the same lower stage. In this case, however, the flip-flop Dm.sub.1 at the lower stage latches a value 0 which is always input to the selector Sm.sub.1 as the signal D.
Accordingly, in case of k=1, the upper stage flip-flops Dp.sub.0 and Dp.sub.1 latch values 0 and 1, respectively, and the lower stage flip-flop Dm.sub.1 latches a value 0 (shown in FIG. 15).
&lt;in case of k=2: input y.sub.k =y.sub.2 =-0.2; y.sub.p =1.6; .beta.=+1; p=0 &gt;
Since -2.ltoreq.y.sub.k -y.sub.p =-0.2-1.6=-1.8.ltoreq.0 is established, the input corresponds to the condition pattern B shown in Table 1. That is, since the parallel path occurs, the values .beta. and y respectively stored in the registers 12a and 12b are set as they are. The comparing circuit 13 outputs the survivor path pattern signal (merge=0) and the data (data=0) to the shift register 121.
In the shift register 121, the flip-flop Dp.sub.0 latches the signal of merge=0. Since merge=0 is established, in accordance with Table 3, the signal (bit) latched by the flip-flop Dp.sub.n at the upper stage is latched by the succeeding stage flip-flop Dp.sub.n+1 at the same upper stage, and the signal (bit) latched by the flip-flop Dm.sub.n at the lower stage is latched by the succeeding stage flip-flop Dm.sub.n+1 at the same lower stage.
Accordingly, in case of k=2, the upper stage flip-flops Dp.sub.0, Dp.sub.1 and Dp.sub.2 latch values 0, 1 and 1, respectively, and the lower stage flip-flops Dm.sub.1 and Dm.sub.2 latch values 0 and 0, respectively (FIG. 15).
&lt;in case of k=3: input y.sub.k =y.sub.3 =2.0; y.sub.p =1.6; .beta.=+1; p=0&gt;
Since y.sub.k -y.sub.p =2.0-1.6=0.4&gt;0 is established, the input corresponds to the condition pattern C shown in Table 1. That is, since the upward divergence occurs, the previous candidate value y.sub.p was defeated by the present value y.sub.k (y.sub.p &lt;y.sub.k was established). In other words, although it was determined that the upward divergence (.beta.=+1) occurred in case of k=0 (p=0), the upward divergence (.beta.=+1) occurred at this time (in case of k=3), so that the parallel path of the upward divergence was selected at the previous time (the path would become discontinuous at k=3 if the upward shift had been selected at k=0).
Then, in accordance with Table 1, the vale .beta. stored in the register 12a is set to +1 and the value y.sub.p stored in the register 12b is set as y.sub.p =y.sub.3 =2.0. Further, the comparing circuit 13 outputs the survivor path pattern signal (merge=1) and the data (data=0) to the shift register 121.
In the shift register 121, the flip-flop Dp.sub.0 latches the signal of merge=1. Further, since merge=1 and data=0 are established, in accordance with Table 3, the selector Sp.sub.n or Sm.sub.n respectively selects the signal B or the signal D of the signals A and B or the signals C and D, which is respectively output therefrom to and then latched by the succeeding stage flip-flop Dp.sub.n or Dm.sub.n.
If the just previous divergence was the upward divergence (.beta.=+1 was established) and further the present divergence is the upward divergence, then it is determined that the signal (bit) latched by the upper stage flip-flop Dp.sub.n as a decoding data candidate is defeated and hence the signal (bit) latched by the lower stage flip-flop Dm.sub.n is latched by the succeeding stage flip-flops DP.sub.n+1 and Dm.sub.n+1 at the upper and lower stages. In this case, however, the upper stage flip-flop Dp.sub.1 latches the value 0 which is always input to the selector Sp.sub.1 as the signal B.
Accordingly, in case of k=3, the upper stage flip-flops Dp.sub.0, Dp.sub.1, Dp.sub.2 and Dp.sub.3 latch the values 1, 0, 0 and 0, respectively, and the lower stage flip-flops Dm.sub.1, Dm.sub.2 and Dm.sub.3 latch the values 0, 0 and 0, respectively (as shown in FIG. 15).
&lt;in case of k=4: input y.sub.k =y.sub.4 =0.2; y.sub.p =2.0; .beta.=+1; p=3&gt;
Since -2.ltoreq.y.sub.k -y.sub.p =0.2-2.0=-1.8.ltoreq.0 is established, the input corresponds to the condition pattern B shown in Table 1. That is, since the parallel path occurs, the values .beta. and y.sub.p respectively stored in the registers 12a and 12b are set as they are. The comparing circuit 13 outputs the survivor path pattern signal (merge=0) and the data (data=0) to the shift register 121.
In the shift register 121, the flip-flop Dp.sub.0 latches the signal of merge=0. Since merge=0 is established, the signal (bit) latched by the flip-flop Dp.sub.n at the upper stage is latched by the succeeding stage flip-flop DP.sub.n+1 at the same upper stage, and the signal (bit) latched by the flip-flop Dm.sub.n at the lower stage is latched by the succeeding stage flip-flop Dm.sub.n+1 at the same lower stage.
&lt;in case of k=5: input y.sub.k =y.sub.5 =-0.4; y.sub.p =2.0; .beta.=+1; p=3 &gt;
Since y.sub.k -y.sub.p =-0.4-2.0=-2.4&lt;-2 is established, the input corresponds to the condition pattern A shown in Table 1. That is, since the downward divergence occurs, it is determined that the previous candidate value is correct (that is, in case of k=3 (p=3), the upward shift of the upward divergence was selected.).
Therefore, in accordance with Table 1, the value .beta. stored in the register 12a is set to -1 and the value y.sub.p stored in the register 12b is set as y.sub.p =y.sub.5 =-0.4. Further, the comparing circuit 13 outputs the survivor path pattern signal (merge=1) and the data (data=1) to the shift register 121.
In the shift register 121, since the flip-flop Dp.sub.0 latches the signal of merge=1 and further merge=1 and data=1 are established, in accordance with Table 3, the selectors Sp.sub.n and Sm.sub.n respectively select the signal A of the signals A and B and the signal C of the signals C and D, which are respectively output therefrom to and then latched by the succeeding stage flip-flops Dp.sub.n and Dm.sub.n.
When the previous divergence was the upward divergence (.beta.=+1 was established) and further the present divergence is the downward divergence, it is determined that the signal (bit) latched by the upper stage flip-flop Dp.sub.n as the decoding data candidate is correct and hence the signal (bit) latched by the upper stage flip-flop Dp.sub.n is latched by the succeeding stage flip-flops DP.sub.n+1 and Dm.sub.n+1 at the upper stage and lower stage.
&lt;in case of k=6: input y.sub.k =y.sub.6 =-0.2; y.sub.p =-0.4; .beta.=-1; p=5&gt;
Since 0.ltoreq.y.sub.k -y.sub.p =-0.2-(-0.4)=0.2.ltoreq.+2 is established, the input corresponds to the condition pattern E shown in Table 2. That is, since the parallel path occurs, the values .beta. and y.sub.p are set as they are. The comparing circuit 13 outputs the survivor path pattern signal (merge=0) and the data (data=0) to the shift register 121.
In the shift register 121, the flip-flop Dp.sub.0 latches the signal of merge=0. Since merge=0 is established, the signal (bit) latched by the flip-flop Dp.sub.n at the upper stage is latched by the succeeding stage flip-flop DP.sub.n+1 at the same upper stage, and the signal (bit) latched by the flip-flop Dm.sub.n at the lower stage is latched by the succeeding stage flip-flop Dm.sub.n+1 at the same lower stage.
&lt;in case of k=7: input y.sub.k =y.sub.7 =-2.0; y.sub.p =-0.4; .beta.=-1; p=5&gt;
Since y.sub.k -y.sub.p =-2.0-(-0.4)=-1.6&lt;0 is established, the input corresponds to the condition pattern D shown in Table 2. That is, since the downward divergence occurs, it is determined that the previous candidate value was defeated. That is, in case of k=5 (p=5), not the downward shift but the parallel shift was selected.
Therefore, in accordance with Table 2, the value .beta. stored in the register 12a is set to -1 and the value y.sub.p stored in the register 12b is set as y.sub.p =y.sub.7 =-2.0. Further, the comparing circuit 13 outputs the survivor path pattern signal (merge=1) and the data (data=0) to the shift register 121.
In the shift register 121, since the flip-flop Dp.sub.0 latches the signal of merge=1 and further merge=1 and data=0 are established, in accordance with Table 3, the selectors Sp.sub.n and Sm.sub.n respectively select the signal B of the signals A and B and the signal D of the signals C and D, which are respectively output therefrom to and then latched by the succeeding stage flip-flops Dp.sub.n and Dm.sub.n.
If the just previous divergence was the downward divergence (.beta.=-1 was established) and further the present divergence is the downward divergence, then it is determined that the signal (bit) latched by the upper stage flip-flop Dp.sub.n as the decoding data candidate was defeated and hence the signal (bit) latched by the lower stage flip-flop Dm.sub.n is latched by the succeeding stage flip-flops DP.sub.n+1 and Dm.sub.n+1 at the upper and lower stages. In this case, however, the upper stage flip-flop Dp.sub.1 latches the value 0 which is always input to the selector Sp.sub.1 as the signal B.
&lt;in case of k=8: input y.sub.k =y.sub.8 =0.2; y.sub.p =-2.0; .beta.=-1; p=7 &gt;
Since y.sub.k -y.sub.p =0.2-(-2.0)=2.2&gt;+2 is established, the input corresponds to the condition pattern F shown in Table 2. That is, since the upward divergence occurs, it is determined that the previous data is correct. In other words, in case of k=7 (p=7), the downward shift occurred.
Therefore, in accordance with Table 2, the value .beta. stored in the register 12a is set to 1 and the value y.sub.p stored in the register 12b is set as y.sub.p =y.sub.8 =0.2. Further, the comparing circuit 13 outputs the survivor path pattern signal (merge=1) and the data (data=1) to the shift register 121.
In the shift register 121, the flip-flop Dp.sub.0 latches the signal of merge=1. Further, since merge=1 and data=1 are established, in accordance with Table 3, the selector Sp.sub.n or Sm.sub.n respectively selects the signal A or the signal C of the signals A and B or the signals C and D, which is respectively output therefrom to and then latched by the succeeding stage flip-flop Dp.sub.n or Dm.sub.n.
When the previous divergence was the downward divergence (.beta.=-1 was established) and further the present divergence is the upward divergence, it is determined that the signal (bit) latched by the upper stage flip-flop Dp.sub.n as the decoding data candidate is correct and hence the signal (bit) latched by the upper stage flip-flop Dp.sub.n is latched by the succeeding stage flip-flops DP.sub.n+1 and Dm.sub.n+1 at the upper stage and lower stage.
Hereinafter, the data are decoded similarly. A bit for causing the condition A or C shown in Table 1 or the condition D or F shown in Table 2 is added to the end of a bit string. If the condition A or C shown in Table 1 or the condition D or F shown in Table 2 is caused, then the values stored by the upper stage flip-flops Dp.sub.1 to Dp.sub.N and the lower stage flip-flops Dm.sub.1 to Dm.sub.N are respectively matched with each other. Therefore, either of the data (bit) latched by the upper stage flip-flop Dp.sub.N and the lower flip-flop Dm.sub.N (for example, by the upper stage flip-flop Dp.sub.N) are successively received to thereby obtain the Viterbi-decoded data.
A magnetic recording and reproducing apparatus or an optical recording and reproducing apparatus, for example, adds an error detecting code such as a CRC (Cyclic Redundancy Check) code, for example, or the like to an ID such as a sector number, a track number or the like in order to improve reliability.
If an equation EQU G(x)=x.sup.16 +x.sup.12 +x.sup.5 +1 (6)
is used as a generating polynomial G(x) of the CRC code, for example, then data of a predetermined bit length BL are divided by the generating polynomial G(x)=x.sup.16 +x.sup.12 +x.sup.5 +1 and a remainder of the division is added to an end of the data.
When an error of the data added with such CRC code is detected, a CRC decoding circuit as shown in FIG. 16 is used.
In the CRC decoding circuit, there are connected in series flip-flops D.sub.1 to D.sub.16 of the same number as the highest degree of the generating polynomial (which is 16 in case of the generating polynomial shown in equation (6)) and there are provided XOR gates (which are indicated by a symbol composed by inserting a symbol + into a symbol .smallcircle. in the figure) at the preceding stage of the flip-flop D.sub.1, between the flip-flops D.sub.5 and D.sub.6 and between the flip-flops D.sub.12 and D.sub.13.
Further, to the XOR gate provided at the preceding stage of the flip-flop D.sub.1, the decoded data are input and further an output from the flip-flop D.sub.16 is fed back. An output of the above XOR gate is input to not only the flip-flop D.sub.1 but also the XOR gates provided between the flip-flops D.sub.5 and D.sub.6 and between the flip-flops D.sub.12 and D.sub.13.
In the CRC decoding circuit thus arranged, an exclusive-OR of a decoded bit string of the predetermined bit length (the bit length of data including the CRC code) BL and the output from the flip-flop D.sub.16 is calculated at the XOR gate provided at the preceding stage of the flip-flop D.sub.1. While the exclusive-OR of the decoded bit string and the output of the XOR gate provided at the preceding stage of the flip-flop D.sub.1 is being calculated at the XOR gates provided between the flip-flops D.sub.5 and D.sub.6 and between the flip-flops D.sub.12 and D.sub.13, the decoded bit string is successively latched by the flip-flops D.sub.1 to D.sub.16, whereby when the last bit of the bit string is input to the flip-flop D.sub.1, the bit string is subjected to a calculation (CRC calculation) in which the bit string is divided by the generating polynomial shown in equation (6).
As a result, if the bits latched by the flip-flops D.sub.1 to D.sub.16 all have values 0, i.e., the decoded bit string of the predetermined bit length BL is completely divided by the generating polynomial shown in equation (6), then it is determined that the bit string has no error. If any one of the bits latched by the flip-flops D.sub.1 to D.sub.16 is not a value 0, i.e., the decoded bit string of the predetermined bit length BL is not completely divided by the generating polynomial shown in equation (6), then it is determined that the bit string has an error.
When the data are decoded by the Viterbi decoder 116 arranged as shown in FIG. 12, it is necessary that the data (bit) are successively shifted by the shift register 21 shown in FIG. 13. Therefore, a processing time is delayed to an extent of the bit number of the number of the flip-flop Dp.sub.n (Dm.sub.n) provided in series in the shift register 121.
When the error of the decoded data is detected by the CRC decoding circuit as shown in FIG. 16, it is necessary that the flip-flops D.sub.1 to D.sub.16 successively latch the bit strings of the predetermined bit length BL. Therefore, a processing time is delayed to an extent of the predetermined bit length BL.
Accordingly, when the error of the data decoded by the Viterbi decoder 116 is detected by the CRC decoding circuit as shown in FIG. 16, the processing time is considerably delayed.
The Viterbi decoder 116 and the CRC decoding circuit are not useful for a portion where there is required quick judgement whether or not data are read from or written on a sector after an ID is decoded, such as an ID portion of the sector or the like. However, if they are applied to such portion in order to improve reliability of the apparatus, then, as shown in the timing diagram of FIG. 17, a long gap must be provided between an end of an ID region of the recording medium corresponding to a timing when the input of the reproduced data of the ID to the Viterbi decoder 116 is terminated and a beginning of a data region corresponding to a timing when a CRC operation in the CRC decoding circuit is terminated (input of the decoded data of the ID from the Viterbi decoder 116 to the CRC decoding circuit is terminated). Therefore, there is then the problem that a recording capacity of the recording medium is lowered.